A cache may be arranged to store data and/or instructions fetched from a memory so that they are subsequently readily accessible by a processor. Hereafter, unless otherwise apparent from the context, the term “data value” will be used to refer to both instructions and data. The cache will store the data value until it is overwritten by a data value for a new location required by the processor. The data value is stored in cache using either physical or virtual memory locations. Should the data value in the cache have been altered then it is usual to ensure that the altered data value is re-written to the memory, either at the time the data is altered or when the data value in the cache is overwritten.
One type of cache is an n-way set associative cache. Each way of the cache comprises a data memory having a plurality of cache lines, each cache line being operable to store a plurality of data values. In addition to the data memory, there is also provided a TAG memory. For each cache line within the data memory, there is provided a corresponding entry within the TAG memory.
Each access request issued by a processor for access to a data value will typically identify an address associated with that data value and that address will include a TAG portion and a set portion. The set portion of the address is used to identify a particular set within the cache. Each set within an n-way set associative cache consists of a single cache line in each of the ways, and hence, by way of illustration, a four way set associative cache will have four cache lines in each set. This means that for a particular data value, there are n possible cache lines in which that cache value can be stored within an n-way set associative cache, namely one cache line in each way.
The data values stored within any particular cache line will share a common TAG portion of their address, and that TAG portion is stored within the associated entry of the TAG memory. Furthermore, all of the data values in a particular cache line relate to a sequence of adjacent data values in memory.
Accordingly, when the processor issues a sequential access request, i.e. an access request in which the address follows a predetermined incremental relationship to the address of the immediately preceding access request, and a hit occurred in a particular way of the cache for that immediately preceding access request, then it is guaranteed that the data value the subject of the current access request will also be found in the same way of the cache, provided that the data value the subject of the immediately preceding access request was not the last data value in a cache line. Thus, for such sequential accesses, it is not necessary to perform any lookup in the TAG memories in order to identify a TAG value matching the TAG portion of the address contained in the access request, since it is already known which way the data value will be found in. Furthermore, it is only necessary to access the data memory of that particular way in order to access that required data value the subject of the sequential access request. Hence, the handling of such a sequential access request within the cache is very power efficient since it is only necessary to access one of the data memories.
This should be contrasted with a non-sequential access, i.e. an access request whose address is not related to that of the immediately preceding access request. For a non-sequential access it is necessary to perform a lookup in each of the TAG memories, and at the same time perform a lookup in each of the data memories, using the set portion of the address as an index into the TAG memory and data memory of each way. If a match is found between the TAG portion of the address of the access request and a TAG value held in one of the TAG memories then the data value is accessed from the corresponding data memory. Hence, for an n-way set associative cache, it can be seen that n TAG memories and n data memories need to be accessed, which represents a significant power cost.
Furthermore, for an access request that is sequential, but relates to an address that is crossing a cache line boundary, the way information pertaining to the immediately preceding access request is no longer valid, and instead the access request has to be treated as non-sequential. Accordingly, in such instances, such a sequential access actually incurs the same power consumption within the cache as a standard non-sequential access.
It is generally desirable to reduce the power consumption of the cache, since this will increase the amount of time that a data processing apparatus including such a cache can be run on battery power, and further will reduce the heat dissipation requirements of the data processing apparatus.